A prevalent load spreading technique today is the spreading of traffic over a set of equal cost paths to a destination node referred to as equal cost multi-path (ECMP). However, in some implementations ECMP can have limitations in supporting operation, administration and management (OAM) functions and difficulty in evenly spreading a traffic load in asymmetrical topologies. ECMP has been implemented by using hashing algorithms and/or modulo operations on labels for multi-protocol label switching (MPLS) traffic, virtual local area network IDs (VLAN IDs) for layer 2 technology, or header information from packets for layer 3 technology. These hashing algorithms and modulo operations are utilize to spread traffic streams over the number of equal cost next hops in a network as a next hop selection mechanism for forwarding traffic.
When a network forwarding device supports ECMP and this capability is enabled and there are multiple paths with the same (or similar) cost towards a specific destination, the network forwarding device will attempt to divide the load evenly across the set of equal cost next hops. Numerous techniques exist for distributing traffic over these equal cost next hops, those techniques with the most desirable properties are those that preserve flow ordering among protocol data units (PDUs), that is, all PDUs that have similar characteristics such as source, destination and header information, can be considered part of the same “flow” and preserving their ordering indicates that they arrive at their destination in the same order that they were sent by the source.
Existing load spreading techniques rely on the use of some form of hashing process that is applied per-PDU by a network forwarding device. Using such hashing techniques allows for large-scale determination of a collection of “flows” based on key fields in a PDU header. For example, a subset of source address and destination address bits can be used as input to a hashing function to group “flows” in such a way that all PDUs traveling from a particular source to a particular destination are considered part of the same gross-flow and forwarding all PDUs that are part of this gross-flow guarantees that no PDU within a subset flow will follow a different path and as a consequence potentially arrive out of order from the rest of the flow.
ECMP and similar hashing-based techniques have limitations in that in any irregular network or in any regular network that is in a failure scenario the load is difficult to evenly distribute across the plurality of equal cost paths. This is because any particular hashing scheme that is selected in an attempt to evenly distribute PDU traffic across the set of paths is selected without regard to the actual layout of the network beyond the immediate set of next hops. The hashing scheme is typically not changed dynamically in a network failure scenario due to the disruption that would be caused, as a result the hashing scheme selected may not produce a roughly even load distribution in the changed network topology.
All hashing schemes are subject to some degree of correlation. The simpler (and thus easier to apply to in-transit PDUs) a hashing scheme is, the more likely correlation is to be a problem. Correlation with these hashing schemes is a phenomenon where a particular path is disproportionally selected by a hashing scheme due to similarities in properties in the PDU traffic that the hashing scheme utilizes for path selection. Elements of the hashing scheme (such as the specific algorithm chosen, the specific bits used as input, etc.) can reduce, but not eliminate the observed correlation for any specific network and topology. Correlation can lead to serious imbalances in distribution of the PDU traffic load, e.g. where one subset of potential paths carries some integral multiple greater than one of the load carried by another subset of the available paths. An ideal hashing scheme would result in a traffic distribution that would appear to be completely random, while retaining the desirable property of consistently forwarding any particular flow along the same path. Attempts to achieve this aim have consistently resulted in approaches that do not achieve this goal for at least some potential forwarding scenarios and/ or these hashing schemes are extremely complicated in implementation and result in delays in PDU forwarding as an artifact of the hashing scheme used.